#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 1e5+10;

int tr1[N],tr2[N],a[N],n,m,BLOCK,l = 1,r = 0,cnt[N],ans1[N],ans2[N];

struct query{int l,r,a,b,bl,id;}q[N];
bool operator < (query x,query y){return x.bl ^ y.bl ? x.bl < y.bl : x.bl & 1 ? x.l < y.l : x.l > y.l;}

void add1(int x,int y){for(;x<=n;x+=x&-x)tr1[x]+=y;}
void add2(int x,int y){for(;x<=n;x+=x&-x)tr2[x]+=y;}
int query1(int x,int y=0){for(;x;x-=x&-x)y+=tr1[x];return y;}
int query2(int x,int y=0){for(;x;x-=x&-x)y+=tr2[x];return y;}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in; BLOCK = sqrt(n); for(int i = 1;i <= n;i++) a[i] = in;
	for(int i = 1;i <= m;i++) q[i].l = in,q[i].r = in,q[i].a = in,q[i].b = in,q[i].bl = (q[i].l - 1)/ BLOCK + 1,q[i].id = i;
	sort(q+1,q+m+1);
	for(int i = 1;i <= m;i++){
		int xl = q[i].l,xr = q[i].r,xa = q[i].a,xb = q[i].b;
		while(l < xl) {add1(a[l],-1);if(!--cnt[a[l]]) add2(a[l],-1);l++;}
		while(l > xl) {l--; add1(a[l],1); if(!cnt[a[l]]++) add2(a[l],1);}
		while(r < xr) {r++; add1(a[r],1); if(!cnt[a[r]]++) add2(a[r],1);}
		while(r > xr) {add1(a[r],-1);if(!--cnt[a[r]]) add2(a[r],-1);r--;}
		ans1[q[i].id] = query1(xb) - query1(xa-1); ans2[q[i].id] = query2(xb) - query2(xa-1);
	}for(int i = 1;i <= m;i++) printf("%d %d\n",ans1[i],ans2[i]);
	return 0;
}

